#include "sort.h"
using namespace std;

// 插入排序
void Sort::Insertsort(vector<int>& arr) {
  int n = arr.size();
  for (int i = 0; i < n - 1; i++) {  // i的区间为[0,n-2]
    int end = i;             // end的初始值为i,即有序的区间为[0-end]
    int key = arr[end + 1];  // key的初始值为arr[end+1],即待插入的元素
    // 寻找插入位置，要插入的位置应该大于等于0
    while (end >= 0) {
      //
      if (arr[end] > key) {
        arr[end + 1] = arr[end];  // 右移元素，腾出位置
        end--;                    // end指向左缩减
      } else {
        break;  // 插入位置找到，退出循环
      }
    }
    arr[end + 1] = key;  // 插入元素
  }
  return;
}

// 希尔排序
void Sort::Shellsort(vector<int>& arr) {
  int n = arr.size();
  int gap = n;       // 初始步长为n
  while (gap > 1) {  // 步长大于1时，进行插入排序
    gap = gap / 2;   // 每次步长递减为原来的一半
                     // 每组进行单独排序
    // 从该组的第一个元素开始，n-gap是防止数组越界
    for (int i = 0; i < n - gap; i++) {  // 步长为gap的区间
      // 执行插入排序
      int end = i;  // end的初始值为i,即有序的区间为[0-end]
      int key = arr[end + gap];  // 待插入元素
      // 寻找插入位置，要插入的位置应该大于等于0
      while (end >= 0) {
        if (arr[end] > key) {
          arr[end + gap] = arr[end];  // 右移元素，腾出位置
          end -= gap;                 // end指向左缩减
        } else {
          break;  // 插入位置找到，退出循环
        }
      }
      arr[end + gap] = key;  // 插入元素
    }
  }
  return;
}

// 选择排序
void Sort::Selectionsort(vector<int>& arr) {
  int n = arr.size();
  int begin = 0;    // 起始位置,最小的元素
  int end = n - 1;  // 终止位置,最大的元素
  while (begin < end) {
    int max_index = end;    // 最大值索引
    int min_index = begin;  // 最小值索引
    // 还没有排序的区间为[begin,end],是闭区间

    // 遍历[begin,end]区间,获取最大值和最小值
    for (int i = begin; i <= end; i++) {
      if (arr[i] > arr[max_index]) max_index = i;
      if (arr[i] < arr[min_index]) min_index = i;
    }
    // 交换最大值和最小值
    swap(arr[begin], arr[min_index]);
    // 如果max_index的位置就是begin,与arr[begin]进行交换后
    // 最大值位置为arr[min_index]了
    if (max_index == begin) {
      max_index = min_index;
    }
    swap(arr[max_index], arr[end]);
    // 缩小区间
    begin++;
    end--;
  }
  return;
}

// 冒泡排序
void Sort::Bubblesort(vector<int>& arr) {
  int n = arr.size();
  int end = n - 1;  // 终止位置,[end,n-1]都是有序的
  // 遍历n-1次,每次遍历就能找到最大值
  for (int i = 0; i < n - 1; i++) {
    bool flag = false;  // 标记是否发生交换
    for (int j = 0; j < end; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换
        swap(arr[j], arr[j + 1]);
        flag = true;  // 发生交换
      }
    }
    if (!flag) break;  // 没有发生交换,说明已经有序,退出循环
    end--;             // 缩小区间
  }
  return;
}

// 快速排序
// 区间内找出基准值 pivot
int Sort::Partition(vector<int>& arr, int left, int right) {
  // 选择左边的元素作为基准值
  int key = arr[left];
  int pivot = left;  // 坑位的索引
  while (left < right) {
    // 右边指针向左移动,直到找到小于等于key的元素
    while (left < right && arr[right] >= key) {
      right--;
    }
    // 交换左右指针指向的元素，并更新坑位
    swap(arr[pivot], arr[right]);
    pivot = right;  // 更新坑位,可以理解为这个位置的元素为空

    // 左边指针向右移动,直到找到大于key的元素
    while (left < right && arr[left] <= key) {
      left++;
    }
    // 交换左右指针指向的元素，并更新坑位
    swap(arr[pivot], arr[left]);
    pivot = left;  // 更新坑位,可以理解为这个位置的元素为空
  }
  arr[pivot] = key;  // 基准值放到坑位
  return pivot;      // 返回坑位的索引
}

// 递归调用
void Sort::Quicksort(vector<int>& arr, int left, int right) {
  if (left >= right) return;                // 递归终止条件
  int pivot = Partition(arr, left, right);  // 找出基准值
  // [left,pivot-1] [pivot+1,right]
  Quicksort(arr, left, pivot - 1);   // 左边递归
  Quicksort(arr, pivot + 1, right);  // 右边递归
}

// 打印数组
void Sort::PrintArr(vector<int>& arr) {
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";  // 输出数组元素
  }
  cout << endl;
}
